Error diffusion is a well known method of processing gray scale images on a binary output device. One of the key ingredients in error diffusion is a requirement to propagate or diffuse the error which is generated by reducing (binarizing) the gray level value of a gray scale image.
Recently, improved features have been added to the typical error diffusion method. Specifically, it has been proposed to utilize high addressability error diffusion. A brief description of high addressability error diffusion will follow.
In explaining the high addressability error diffusion process, it is assumed that the input gray level at pixel location i and pixel location i+1 is represented by V.sub.i and V.sub.i+1, respectively. The pixel values are assumed to be 8 bit integers wherein, for the sake of explanation, 0 denotes white and 255 denotes black. The rendering error, at a resolution lower than the addressability resolution, that passes from upstream pixels to the downstream pixel location is denoted by e.sub.i.
It is noted that a feature of high addressability involves interpolation between pixels, the creation of subpixels. This interpolation impacts the high addressability error diffusion process. More specifically, depending on the way the interpolation is done, distinct outputs can be obtained utilizing a high addressability error diffusion process. One such method of interpolation is as follows.
FIGS. 1-7 illustrate the computational steps required to perform high addressability error diffusion using a particular interpolation scheme. Initially, as illustrated in FIG. 1, the pixel value V.sub.i and V.sub.i+1 are obtained. The actual pixel values are graphically illustrated in FIG. 1, wherein the pixel value V.sub.i represents the pixel value at the subpixel position 0 and the pixel value V.sub.i+1 represents the pixel value at the N-1 subpixel. In FIG. 1, the pixel values range from 0 to 255 utilizing a conventional eight bit dataword to represent the multi-level gray value of the image data to be process. It is noted that any range can be utilized to represent the gray level value of the image data; for example, 0 to 511,0 to 127, etc.
After obtaining the initial pixel values of V.sub.i and V.sub.i+1, a diffused error component e.sub.i (the accumulated error from previous pixel binarization processes) is added to the pixel values V.sub.i and V.sub.i+1. It is noted that the error component e.sub.i consists of two components, e.sub.FIFO and e.sub.FB, where e.sub.FIFO is the summed error component stored in a line buffer and e.sub.FB is the feedback error component. The adding of the error component e is illustrated graphically in FIG. 2.
After adding the diffused error component, the interpolated subpixel values are computed, as illustrated in FIG. 3. For example, the interpolated subpixel values are B.sub.n =P0.sub.i +n (Pl.sub.i -P0.sub.i)/N for n=0 to N-1, where N is the selected high addressability characteristic. It is noted that the value P0.sub.i is equal to V.sub.i+1 +e.sub.i and P1.sub.i is equal to V.sub.i+1 +e.sub.i.
After computing the interpolated subpixel values, each interpolated subpixel value is compared to a threshold level. In the example illustrated in FIG. 4, the threshold value is 128. It is noted that this threshold value can be any value within the range of the image data depending upon the desired results. In this example, each subpixel which has a value greater than or equal to 128 is set ON.
Next, the desired output (P0.sub.i +P1.sub.i)/2 is computed. This computing of the desired output is graphically illustrated in FIG. 5. After computing the desired output, the actual output is computed. In this example, the actual output is equal to n*255/N where n is the number of subpixels that have been turned ON as the result of the comparison illustrated in FIG. 4. A graphical representation of the computed actual output is shown in FIG. 6.
Once the desired output and the actual output have been computed, the error diffusion method computes the error to be propagated downstream. This error is computed as the desired output minus the actual output. A graphical representation of this computation is shown in FIG. 7.
As illustrated in FIG. 7, the error is calculated to be e.sub.i+1 -(P0.sub.i -P1.sub.i)/2-(n*255/N).In this instance, the error e.sub.i+l represents the error from the present binarization process. As in all conventional error diffusion processes, the error from the binarization process is distributed to downstream pixels. The distributing of the error e.sub.i+1 to downstream pixels is illustrated in FIG. 8. In this example, the distribution of error utilizes a set of error diffusion coefficients which allow fast processing by simple bit shifting. FIG. 8 illustrates the coefficients associated with each pixel location. An example of the exact coefficients are discussed in U.S. patent application, Ser. No. 08/167,758. The entire contents of Ser. No. 08/167,758 are hereby incorporated by reference.
To more readily understand the high addressability error diffusion method, a more detailed description is disclosed in copending application, U.S. patent application Ser. No. 08/285,326, filed concurrently herewith and will be discussed below.
There are many methods of rendering gray images on an output device. Moreover, error diffusion can render complex images that contain a mixture of text and picture reasonably well. This utilization of error diffusion eliminates the need to have image segmentation to separate the text from the picture so that the picture aspect of the document can be screened and the text aspect of the document can be threshold.
FIG. 22 illustrates a typical error diffusion technique. In Step S1 of this process, the video signal for pixel X is modified to include the accumulated error diffused to this pixel from previous threshold processes. The modified video signal value (X) is compared at Step S2 with the value 128, assuming a video range between 0 and 255. If Step S2 determines that the modified video signal value (X) is greater than or equal to 128, the process proceeds to Step S4 wherein a value is output to indicate the turning ON of pixel X. The process then proceeds to calculate the error associated with the threshold process at Step S6 wherein this error, Y, is calculate as being X -255.
On the other hand, if Step S2 determines that the modified video signal value (X) is less than 128, a signal is output at Step S3 indicating that the pixel X is to be turned OFF. The process then proceeds to Step S5 wherein the error, Y, is calculated as being equal to the value X.
The error calculated in either Steps S5 or S6 is multiplied by weighting coefficients and distributed to downstream pixels in Step S7. Thus, the error from the threshold process is diffused to adjacent pixels. The coefficients conventionally used to diffuse the error to adjacent downstream pixels are illustrated in FIG. 23.
In FIG. 23, X represents the current pixel being thresholded. The weighted error from this threshold process is diffused to adjacent downstream pixels according to preselected coefficients. For example, the weighting coefficient for the next pixel in the same scanline conventionally is 7/16, whereas the coefficient for the pixel that is one over in the fast scan direction and one down in the slow scan direction from the currently processed pixel is 1/16.
This method provides good results, but with advances in marking or printing technology, a new error diffusion method is needed. More specifically, it has become possible to pulse width modulate a laser to print images with high addressability. To use error diffusion in combination with high addressability, one cannot simply perform the error diffusion at the high spatial resolution corresponding to the high addressability because the resulting subpixels would be too small for a typical print engine to render. Thus, it is desired to develop an error diffusion technique which can be effectively utilized with the present day highly addressable image output terminals without producing subpixels too small for rendering.
In describing the present invention, it is assumed that the video value in a range between 0 and 255. However, any chosen range for the video signal can be utilized in conjunction with the present invention. As described above, in conventional error diffusion methods, the printing of the pixels is determined by comparing a modified input with a threshold. The modified input video signal is the input video signal, V, plus an accumulated error term, ei, determined from the processing of previous pixels. If the modified input video signal of the pixel is greater than or equal to the threshold, the output is a logical one and an error term of V+e.sub.i - 255 is propagated to the downstream pixels. If the modified input video signal is less than the threshold, the logical output is 0 and an error of V +e.sub.i is propagated downstream.
It is noted that the present invention is being described for a binary system. However, the concepts the present invention are readily applicable to four level systems, etc.
To extend the conventional error diffusion process to a high addressability environment, the binarization (threshold) is performed at a higher spatial resolution, but the error computation and propagation is performed at the original lower spatial resolution. This splitting of the process substantially prevents or reduces the number of isolated subpixels, thereby maintaining high image quality. This high resolution/low resolution method of the present invention will be explained in more detail below.
In explaining the high addressability error diffusion process, it is assumed that the input gray level at pixel location i and pixel location i+1 is represented by V.sub.i and V.sub.i+1, respectively. The pixel values are assumed to be 8 bit integers wherein, for the sake of explanation, 0 denotes white and 255 denotes black. The rendering error, at the lower resolution, that passes from upstream pixels to the downstream pixel location is denoted by e.sub.i.
It is noted that a feature of high addressability involves interpolation between pixels, the creation of subpixels. This interpolation impacts the high addressability error diffusion process. More specifically, depending on the way the interpolation is done, two distinct outputs can be obtained utilizing the high addressability error diffusion process of the present invention. Each one of these distinct outputs will be discussed below.
As noted above, the high addressability error diffusion process of the present invention produces two distinct outputs depending upon the interpolation scheme. With respect to a first interpolation scheme, the steps for determining the printing or rendering of a subpixel are as follows.
Initially, the modified pixel values P0.sub.i =V.sub.i-1 +e.sub.i-1 =P1.sub.i-1 and P1.sub.i =V.sub.i +e.sub.i are computed at two locations corresponding to the input resolution. In this example, as illustrated in FIG. 24, the subpixels are denoted by 0 to N-1. In FIG. 24, the high addressability characteristic, N, is equal to 4.
As illustrated in FIG. 24, a line is drawn to connect the values P0 and P1. (The subscripts have been dropped for simplicity.) Moreover, a dotted line is drawn to represent a threshold value of 128. (Again, it is noted that 0 to 255 is the range of the video signal; however, any range can be utilized.) The intersection of the line connecting P0 and P1 and the line representing the threshold at 128 determines which subpixels are to be rendered or printed. The X coordinate of the point of intersection is determined and normalized to N by the equation X=N (128-P0)/(P1-P0).
Next, it is determined which subpixels are to be turned ON. If X is less than or equal to 0 and if P1 is greater than or equal to 128, all the subpixels are ON; otherwise, all the subpixels are OFF. This decision represents the complete rendering or non-rendering of the pixel. To determine a partial rendering of the whole pixel, a subpixel analysis must be performed. In this instance, the value X must be compared to the individual subpixel values.
It is noted, as illustrated in FIG. 24, that the value of X does not necessarily compute to a whole number or subpixel, thereby making any analysis include a fractional component. To avoid this, X is converted to a whole number or subpixel value. For this conversion, n is allowed to be equal to the truncated integer value of X. The values n and X can then be utilized to determine which subpixels are to be turned ON and which subpixels are to be turned OFF. More specifically, if X is greater than 0, but less than n, and if P1 is less than 128, only the subpixels from 0 to n are turned ON and the rest of the subpixels are turned OFF; otherwise, the subpixels from 0 to n are turned OFF and the rest are turned ON. If X is greater than or equal to n and if P0 is greater than or equal to 128, all subpixels are turned ON; otherwise, all subpixels are turned OFF.
This threshold process produces an error which needs to be propagated to downstream pixels. Moreover, as noted above, the error needs to be at the original low resolution input. The conversion to the original resolution is realized by determining the difference between the desired output, (P0+P1)/2, and the actual output, namely b*255/N where b is the number of subpixels that were turned ON. The converted error is then multiplied by a set of weighting coefficients and distributed to the downstream pixels.
FIG. 25 illustrates the actual method utilized to carry out the interpolation and error distribution process described above. In FIG. 25, at Step S10, the modified video input signal is divided into N subpixel values. At Step S20, the values P0.sub.i and P1.sub.i are calculated as described above. Next, at Step S30, the X-coordinate of the point of intersection is determined and normalized by multiplying the difference between 128 and P0 by the value N and dividing this product by the difference of P1 and P0. At Step S40, the normalized value X is compared with the value 0. If X is less than or equal to 0, Step S50 compares the value P1 with the value 128. If the value P1 is greater than or equal to 128, all the subpixels are set to an ON state at Step S60. However, if P1 is less than 128, Step S70 sets all the subpixels to an OFF state.
On the other hand, if Step S40 determines that X is not less than or equal to 0, Step S90 determines the integer value of X and sets this integer value equal to Y. At Step S100, the integer value Y is compared with the values 0 and N. If the value Y lies between 0 and N, Step S110 determines whether the value P1 is less than or equal to 128. If the value P1 is less than or equal to 128, Step S120 sets the subpixels 0 to Y to the ON state and the subpixels Y+1 to N to the C)FF state. However, if Step S110 determines that the value P1 is greater than 128, Step S130 sets the subpixels 0 to Y to the OFF state and the subpixels Y+1 to N to the ON state.
If Step S100 determines that the value Y is not between the values 0 and N, Steps S140 determines whether the value P1 is greater than or equal to 128. If the value P1 is greater than or equal to 128, Step S160 sets all subpixels to the ON state. However, if Step S140 determines that the value P1 is less than 128, Step S150 sets all the subpixels to the OFF state.
Upon completing the processes at either Steps S60, S70, S120, S130, S150, or S160, the error diffusion method of the present invention proceeds to Step S170. At Step S170, the number of ON subpixels is calculated and set equal to Z. Next, at Step S180, the error to be propagated to the downstream pixels is calculated. Namely, the error is calculated to represent the original low spatial resolution. Upon calculating the error in Step S180, Step S190 multiplies the error by weighting coefficients and distributes the weighted error terms to downstream pixels.
The second interpolation method with respect to implementing the high addressability error diffusion method of the present invention will be describe as follows.
Initially, the modified pixel values P0.sub.i =V.sub.i +e.sub.i and P1.sub.i =V.sub.i+1 +e.sub.i are computed. FIG. 26 illustrates the values P0 and P1 for the second version of the high addressability error diffusion method of the present invention. As in the first method, the subpixels are denoted by 0 to N-1 wherein, as in the previous case, the high addressability characteristic is N=4.
The interpolated subpixel values are computed as B.sub.n =P0+n(P1-P0)/N for n=0 to N-1. The interpolated subpixel values are then compared with a threshold value which in the preferred embodiment is 128, assuming that the video value ranges from 0 to 255.
If B.sub.n is greater than or equal to 128, the subpixel is turned ON; otherwise, the subpixel is turned OFF. In the second version, the error to be propagated to downstream pixels is computed as the desired output, (P0+P1)/2, minus the actual output, namely, y*255/N wherein y is the number of subpixels turned ON. The error is then multiplied by a set of weighting coefficients and distributed to the downstream pixels as in the first version.
FIG. 27 illustrates the process utilized in the second interpolation version of the high addressability error diffusion method of the present invention. As in the FIG. 4, the inputted modified video signal is divided into N subpixel units at Step S10. At Step S200, the P0 and P1 values are computed as noted above. At Step S210, the values Y and Z are set equal 0, wherein Y denotes the number of subpixels which are to be turned ON and Z denotes the addressability factor. At Step S220, Z is compared with N to determined whether all the subpixels within the modified video signal have been thresholded. If it is determined that subpixels remain to be thresholded, the process moves to Step S230 wherein the next subpixel value is computed. Step S240 then compares the computed subpixel value with the threshold value, namely 128. If the subpixel value is greater than or equal to the threshold value, Step S260 sets the subpixel value to the ON state, and Step S270 increments the value Y indicating the number of subpixels that are set ON. However, if the subpixel value is less than 128, Step S250 sets the subpixel value to OFF.
Upon the completion of either Step S250 or Step 270, the process proceeds to Step S280 wherein the high addressability value Z is incremented. This subroutine is repeated until all subpixel values within the modified video signal are compared with the threshold value. Upon completing the comparison of all subpixel values, the process advances to Step S290 wherein the number of 0N subpixels are calculated. At Step S300, the error from the threshold process is calculated so that the value represents the original lower spatial resolution. Upon calculating the error, Step S310 multiplies the error by weighting coefficients and distributes the error to downstream pixels.
FIG. 28 illustrates the high addressability relationship between adjacent pixels utilizing the first interpolation version of high addressability error diffusion method. More specifically, it is noted that the P1 value of the present pixel is utilized as the P0 value for the next pixel.
On the other hand, FIG. 29 illustrates the high addressability relationship between pixels utilizing the second interpolation version of the high addressability error diffusion method. In this case, there is discontinuity between the P1 value of the previous pixel and the P0 value of the present pixel. Thus, from these two Figures, it can be seen that the error output from the two versions of the high addressability error diffusion methods will be different.
Although the above enhancement significantly improves the print quality of the images rendered via error diffusion, this improvement tends to make the computations more complex in terms of hardware design and time consuming. One of the most important drawbacks of this high addressability error diffusion improvement has been the time needed to make the complex computations. Although the computations can be implemented in a software environment, the time needed to produce binarized image data for rendering is too long to readily implement such a solution in mid-speed to high-speed printing or image rendering devices. More specifically, the exact correspondence between the high addressability error diffusion computations in software to that which is implemented in hardware is different due to the speed requirements imposed by a system's throughput specification. Therefore, it is desirable to design an unique hardware implementation of the high addressability error diffusion method to meet the time constraints of the present day image rendering devices.